Definition(s)

Pollard's rho algorithm is an algorithm for integer factorization. It was invented by John Pollard in 1975. It uses only a small amount of space, and its expected running time is proportional to the square root of the size of the smallest prime factor of the composite number being factorized.

For an awesome tutorial check this.

Pollard's Rho Algorithm Scheme

a, b = 2, 2;

while ( b != a ){
   a = f(a);     // a runs once
   b = f(f(b));  // b runs twice as fast
   p = GCD(| b - a |, N);

   if ( p > 1)
       return "Factor: p";
}

return "Failure"

Algorithm(s)



In [21]:

    
from math import gcd
from sympy.ntheory import isprime  # primality test
import random



In [22]:

    
def pollards_rho(n, seed=2, f=lambda x: x ** 2 + 1):
    if n % 2 == 0:
        return 2

    a, b, d = seed, seed, 1
    while d == 1:
        a = f(a) % n
        b = f(f(b) % n) % n
        d = gcd(a - b, n)

    return None if d == n else d



In [32]:

    
def impl_factor(n):
    if n < 2:
        return []

    if isprime(n):
        return [n]

    f = pollards_rho(n)
    while f is None:
        a = random.randrange(2, 10 ** 6)
        b = random.randrange(2, 10 ** 6)
        f = pollards_rho(n, seed=b, f=lambda x: x ** 2 + a)

    tmp, factors = impl_factor(f), []
    while n % f == 0:
        factors += tmp
        n = n // f

    return factors + impl_factor(n)

def factor(n):
    fact = impl_factor(n)
    fact.sort()
    return fact

Run(s)



In [33]:

    
factor(100)









    Out[33]:





[2, 2, 5, 5]



In [34]:

    
factor(32131245432423)









    Out[34]:





[3, 773, 1973, 7022629]



In [35]:

    
factor(2 ** 5 * 3 ** 10 * 5 * 7 ** 2)









    Out[35]:





[2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 7, 7]



In [39]:

    
factor(213122112213321312321312)









    Out[39]:





[2, 2, 2, 2, 2, 3, 3, 7187077, 102963601763837]



In [40]:

    
factor(567843720532049232390851243214723895239171032)









    Out[40]:





[2, 2, 2, 11743, 1430357, 4225862227183602989314916784386129]